/**
 * 这样写的无论是时间复杂度和空间复杂度都太高了，可以通过双指针来降低空间复杂度
 * 在leetcode中，提出了一种【划分数组】 的写法，这种写法的时间复杂度为 O(log(n +
 * m))
 */
#include <iostream>
#include <vector>
#include <array>
using namespace std;
class Solution {
public:
  double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    int *v = new int[1000007];
    int i = 0, j = 0, k = 0;
    while (i < nums1.size() && j < nums2.size()) {
      if (nums1[i] <= nums2[j]) {
        v[k++] = nums1[i++];
      } else {
        v[k++] = nums2[j++];
      }
    }
    while (i < nums1.size()) {
      v[k++] = nums1[i++];
    }

    while (j < nums2.size()) {
      v[k++] = nums2[j++];
    }

    if (k & 1)
      return v[k / 2];
    else
      return (v[k / 2 - 1] + v[k / 2]) * 1.0 / 2;
  }
};

int main() {
  vector<int> nums1{1, 3};
  vector<int> nums2{2, 4};
}